As international standardization in moving image encoding in recent years, Moving Picture Experts Group (MPEG) of International Organization for Standardization/International Electrotechnical Commission (ISO/IEC) is known. MPEG corresponds to ISO/IEC JCT1/SC29/WG11, and the international standardization thereof includes a technology for encoding screen content video. The screen content video is video generated by computer graphics or the like, and pixel values of the screen content video often have a high redundancy.
As a technology for promoting encoding of the screen content video above, palette encoding is known. In palette encoding, several indices are associated with pixel values of pixels in one block, and the pixel values are encoded by transmitting the indices instead of the pixel values. The number of bits of the index is smaller than the number of bits of the pixel value. Therefore, compression efficiency of the entirety of video is improved by transmitting the indices instead of the pixel values.
FIG. 1 illustrates an example of palette encoding. An image 101 includes 64 (8×8) pixels, and a palette 103 is generated from respective pixel values of the image 101. Each entry in the palette 103 corresponds to color included in the image 101, and includes an index and a palette value. The index is a code indicating color, and the palette value is a pixel value indicating color. In this example, (R, G, B) is used as the pixel value. The palette 103 is also referred to as a palette table.
An index map 102 is generated by replacing respective pixel values of the image 101 with the indices by using the palette 103. An encoding result of the image 101 is generated by encoding the index map 102 and the palette 103.
Respective values of R, G, and B are expressed by 8 bits, and therefore an amount of information per pixel of the image 101 is 24 (8×3) bits, and an amount of information of the entirety of the image 101 is 1536 (24×64) bits.
Meanwhile, each of the indices is expressed by 3 bits, and therefore an amount of information of the index map 102 is 192 (3×64) bits. In addition, the palette value is expressed by 24 bits, and therefore an amount of information of the palette values included in the palette 103 is 120 (24×5) bits. Accordingly, an amount of information of the index map 102 and the palette 103 is 312 (192+120) bits, and is reduced to about ⅕ the amount of information of the image 101.
Screen content encoding of High Efficiency Video Coding (HEVC) supports both lossy encoding and lossless encoding. Lossless encoding is encoding in which a decoding result of an encoded image completely matches an original image to be encoded, and lossy encoding is encoding that allows a decoding result to be distorted, compared with an image to be encoded.
An object of lossy encoding is to achieve an optimum ratio of distortion to a bit rate, or to minimize distortion under the restriction of the bit rate. A high bit rate used in lossless encoding is not available in all situations.
Meanwhile, in palette encoding, respective pixel values can be encoded in any of the following modes.
(1) Escape Mode
A pixel value is directly encoded without mapping a pixel value on an index map, and an escape code is generated. In the case of lossy encoding, a pixel value is quantized and encoded in order to reduce the number of bits.
(2) Index Mode
In encoding, a pixel value is replaced with an index, and in decoding, a pixel value that corresponds to an index is extracted from a palette, and the index is replaced with the extracted pixel value. In the case of lossy encoding, a pixel value indicated by an index may be different from an original pixel value before encoding.
Assume that, within a block to be encoded, a pixel value is specified by nb_cc color components, and that the respective color components are expressed by ndepth bits. When arithmetic encoding is not performed after palette encoding, the number of bits nb_bit_esc to transmit one escape code is expressed by using a quantizing value Q according to the following expression.nb_bit_esc=nb_cc*ln2(2ndepth/Q)  (1)
In this case, the number of bits nb_bit_pal to transmit one palette value in a palette is expressed according to the following expression.nb_bit_pal=nb_cc*ndepth  (2)
When a block to be encoded is encoded by using nb_index different indices, the number of bits nb_bit_ind to transmit one index is expressed according to the following expression.nb_bit_ind=ln2(nb_index)  (3)
Distortion of a decoding result can be reduced more efficiently by adding an entry to a palette than by using an escape code. However, as is apparent from expressions (1) to (3), a larger number of bits are generated by adding an entry in a palette than by using an escape code.
In a method for generating a palette by focusing on approximating an image, a range of pixel values in which it is considered appropriate to reference a plurality of pixel values by using the same index is specified first. This range can be derived from a quantizing coefficient QP that has been associated with a block to be encoded. Then, pixels within the block to be encoded are scanned, and when pixel values of a plurality of pixels belong to the same pixel-value range in which the pixel values of the plurality of pixels are referenced by using a unique index, the pixels are grouped. Only when a pixel value of the scanned pixel does not belong to a pixel-value range of any of the entries in the palette, a new entry is generated in the palette.
FIG. 2 illustrates an example of a palette generation method. A histogram 201 illustrates an appearance frequency of each of the pixel values within a block to be encoded. In this example, one-dimensional pixel value is used for simplification.
When one pixel at a time is selected from a block to be encoded, and a pixel value of the selected pixel belongs to a pixel-value range of an existing entry in a palette, the pixel is associated with the existing entry. When the pixel value of the selected pixel does not belong to a pixel-value range of any of the entries, a new entry is generated by using the pixel value of the selected pixel as a palette value. When all of the pixels have been selected, a mean value of pixel values of pixels that have been associated with each of the entries is calculated, and palette values of respective entries are replaced with the calculated mean value such that the entries in the palette are updated only once.
Arrows 211 to 214 respectively indicate updated palette values of entries having the indices “0” to “4”. Range [0] to Range [4] respectively indicate updated pixel-value ranges of the entries having the indices “0” to “4”.
A technology is also known in which, in image compression that associates pixels having the same color included in an image with the same index, an index of a pixel that is long in distance is separated, or indices of pixels having approximate colors are consolidated (see, for example, Patent Document 1). A technology is also known in which a distribution on a color space of image data is divided into clusters, the divided clusters are repeatedly divided, and pixel data that belongs to each of the clusters is replaced with representative color by using the center of the cluster as the representative color (see, for example, Patent Document 2).
Patent Document 1: Japanese Laid-open Patent Publication No. 2010-157899
Patent Document 2: Japanese Laid-open Patent Publication No. 4-61558